package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.ListNode;
import com.cuz.daileetcode.utils.ListNodeUtils;
import org.w3c.dom.Node;

import java.util.HashMap;

public class Day28_1 {

    /***
     * 一种新型的链表节点
     */
    static class Node {

        int value;
        Node next;
        /**
         * 指向链表中任意一个指针
         */
        Node rand;

        Node(int value) {
            this.value = value;
        }
    }

    /***
     * 复制一个由Node构成的单向五环链表
     * 同一个node的next 和rand 都需要复制
     *
     * 使用hashMap 复制每一个节点
     * 时间复杂度O(N)
     * 空间复杂度O(N)
     * @return Node 复制生成的新链表头节点
     */
    public static Node copyNodeLinkedListNoCircle1(Node head) {
        // key 是原链表中的节点 value是新复制产生的节点
        HashMap<Node, Node> memory = new HashMap<>();
        Node temp = head;
        //初始化map，key是原节点 value是复制节点
        while (temp != null) {
            memory.put(temp, new Node(temp.value));
            temp = temp.next;
        }
        //进行复制
        temp = head;
        while (temp != null) {
            //让复制节点的next，指向原节点next的复制节点
            memory.get(temp).next = memory.get(temp.next);
            //让复制节点的rand，指向原节点rand的复制节点
            memory.get(temp).rand = memory.get(temp.rand);
            temp = temp.next;
        }
        //返回复制后的head
        return memory.get(head);
    }

    /***
     * 复制一个由Node构成的单向五环链表
     * 同一个node的next 和rand 都需要复制
     *
     *
     * 时间复杂度O(N)
     * 空间复杂度O(1)
     * @return Node 复制生成的新链表头节点
     */
    public static Node copyNodeLinkedListNoCircle2(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node temp = head;
        //原节点假设为 1->2->3   (1 rand->3）
        //生成复制节点，让链表变为 1->1(复制)->2->2（复制）->3->3(复制) rand不变
        while (temp != null) {
            Node copy = new Node(temp.value);
            copy.next = temp.next;
            temp.next = copy;
            //跳过复制复制节点 继续复制
            temp = temp.next.next;
        }
        //原节点
        temp = head;
        //复制生成的节点
        Node tempCopy = temp.next;
        Node newHead = head.next;
        while (true) {
            //原节点的下一个是复制节点的下一个，用于还原原链表
            Node sourceTempNext = tempCopy.next;
            //复制节点的下一个 是复制节点的下一个的下一个 画图！
            if (tempCopy.next!=null){
                tempCopy.next = tempCopy.next.next;
            }
            //复制节点的rand 是原节点rand的下一个 画图
            if (temp.rand!=null){
                tempCopy.rand = temp.rand.next;
            }
            //还原原链表
            temp.next = sourceTempNext;
            temp = sourceTempNext;
            if (temp == null) {
                break;
            }
            //移动复制节点·
            tempCopy = temp.next;
        }
        //返回复制后的head
        return newHead;
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node1.rand = node3;
        node3.rand = node4;
        node2.rand = node4;
        printNode(node1);
        Node copy1 = copyNodeLinkedListNoCircle1(node1);
        printNode(copy1);
        Node copy2 = copyNodeLinkedListNoCircle2(node1);
        printNode(copy2);
        printNode(copy1);
    }

    private static void printNode(Node node) {
        StringBuilder sbNext = new StringBuilder();
        StringBuilder sbRand = new StringBuilder();
        while (node != null) {
            sbNext.append(node.value).append("->");
            if (node.rand != null) {
                sbRand.append(node.value)
                        .append("->r")
                        .append(node.rand.value)
                        .append("\n");
            }
            node = node.next;
        }
        System.out.println(sbNext.toString());
        System.out.println(sbRand.toString());
        System.out.println();
    }
}
